1. Field of the Invention
The present invention relates to a Fourier transform apparatus for performing Fourier transform used for processes such as signal analysis, signal compression and decoding.
2. Description of the Related Art
Fourier transform is indispensable for the processes such as signal analysis, signal compression and decoding. The Fourier transform is based on the idea that "any periodic function can be represented as the sum of trigonometric functions". A non-periodic signal is considered as a function having an infinite cycle.
Recently, discrete Fourier transform has often been used. A cycle of a sample signal obtained from N sample values of t=0 to t=(N-1) is T=N. A frequency f.sub.N of this signal is given by the following expression (1): EQU f.sub.N =1/N (1)
A component of the frequency f.sub.N is a fundamental-wave component, whereby a harmonic-wave component having a frequency k/N equal to the frequency f.sub.N multiplied by an integer can be obtained. By using these frequencies, the following expressions of discrete Fourier transform and inverse discrete Fourier transform can be defined based on the definition of the Fourier transform.
Fourier-transform expression (represented by sine-wave and cosine-wave components): ##EQU1## PA1 Inverse Fourier-transform expression (represented by sine-wave and cosine-wave components): ##EQU2## PA1 Fourier-transform expression (represented by a complex number): ##EQU3## PA1 Inverse Fourier-transform expression (represented by a complex number): ##EQU4## PA1 Fourier-transform expression (represented by a rotator): ##EQU5## PA1 Inverse Fourier-transform expression (represented by a rotator): ##EQU6## PA1 (1) the algorithm must be changed dependent upon hardware. PA1 (2) Since a special operation is performed, data processing other than FFT is adversely affected. PA1 (3) The accuracy is limited by the speed. PA1 (4) Power consumption is increased with an increase in clock frequency.
where g(n) is a sample signal, and a(n/N) and b(n/N) are Fourier coefficients.
Each of the above expressions, Expressions (2) and (3), is a Fourier expansion expression in which the sine-wave component and cosine-wave component are separated.
Moreover, each of the above Fourier expansion expressions is represented by a complex number by using the following Expression (4): EQU G(n/N)=a(n/N)+jb(n/N) (4)
Moreover, G(n/N) and G.sub.n, are simplified as g(n) and g.sub.n, respectively, and each of the above Fourier-transform expressions is represented by a rotator T given by the following Expression (7): EQU T=exp(-j2.pi./N) (7)
Each of the above Fourier-transform expressions requires an enormous amount of calculation. Therefore, it is difficult to apply such Fourier-transform expressions directly to an actual operation. As a result, more practical "fast Fourier transform" (hereinafter, simply referred to as "FFT") is used.
The FFT is an algorithm wherein the number of multiplying operations of sample signal g.sub.k and rotator T.sup.nk as well as the number of adding and subtracting operations represented by .SIGMA. in a transform expression are significantly reduced.
The FFT is applied in a variety of fields, and numerous types of algorithms have been proposed for the FFT. Each such algorithm has respective specific characteristics in terms of simplicity, operation speed, software-program configuration, advantageous property for implementing hardware, or the like. Among these, the FFT with a radix of 2 is most typically used.
The FFT with a radix of 2 is as follows:
First, it is assumed that the number N of sample values is 2.sup.n (where n is an integer). ##EQU7##
When a coefficient 1/N is omitted, the following Fourier-transform expression can be obtained: ##EQU8##
In the case of, for example, N=2.sup.n0, this algorithm can be utilized n0 times, as shown in FIG. 7.
In FIG. 7, DFT indicates discrete Fourier transform. In the case of, for example, N=2.sup.4, the algorithm is repeated four times.
The algorithm is primarily configured from a basic operation called "butterfly operation". In order to implement the butterfly operation, a bit-reversal method of input data and coefficient is used.
Only the fast Fourier transform has been mentioned herein. The operation of inverse Fourier transform is substantially the same as that of the fast Fourier transform, except that G.sub.k and g.sub.n are exchanged each other. Therefore, description thereof is omitted.
Other specific examples include the techniques disclosed in Japanese Laid-Open Publication Nos. 5-189470, 5-174046 and 5-189471, respectively.
Japanese Laid-Open Publication No. 5-189470 relates to a method for performing time-series data input type Fourier transform, and discloses Fourier transform which is performed in a digital manner. In this method, a number of operation devices and buffers are employed together with the above-mentioned FFT algorithm to perform Fourier transform In real time. This method is characterized in that the process is initiated before all of N data have been collected.
Japanese Laid-Open Publication No. 5-174046 shows a circuit configuration wherein the butterfly operation is performed in a digital manner by using a multiplier or the like as an operation circuit.
In Japanese Laid-Open Publication No. 5-189471, a butterfly-type operation device performs FFT in a pipeline manner by using a bit-reversal addressing technique or the like. This is a typical method for implementing an FFT processor.
The above-mentioned FFT algorithm is not problematic in the case of off-line data analysis using a high-level language. However, in the case where on-line data processing is conducted by using DSP (Digital Signal Processor), that is, in the case where audio data or image data which has been compressed by Fourier transform is reproduced, for example, in real time, the FFT algorithm has some disadvantages as follows:
Since software is dependent upon the hardware, new software and a new algorithm must be produced when the hardware is changed, whereby the development period is increased;
In order to implement the bit-reversal of the butterfly operation, special addressing must be conducted by hardware. Therefore, when general-purpose processes are simultaneously conducted by the same hardware, a long instruction code is required. As a result, the hardware is not efficiently utilized, as well as an instruction-memory capacity is increased, leading to an increase in the cost;
In order to increase the processing accuracy, the number of bits must be increased to some extent. According to the FFT algorithm, a number of multiplying and adding operations are performed, whereby the speed (clock) is limited in order to assure carrier processing of such operations; and
The on-line data processing by DSP must be conducted at a high speed. It is a common technique to increase a clock frequency in order to perform the algorithm at a higher speed. In a digital circuit, however, power consumption is increased proportionally to the increase in a clock frequency. This is not advantageous for portable equipment, since, in the portable equipment, low power consumption is desirable in order to utilize a battery as long as possible.
For example, TMS320C50 by TEXAS INSTRUMENTS INC. requires 28,951 cycles for an FFT operation when the number of sample values is N=64 (which corresponds to 72.38 .mu.s when a clock frequency is 40 MHz). Similarly, TMS320C50 requires 15,890 cycles when N=256, and 82,761 cycles when N=1,024. Thus, in the case where a number of cycles are required for the operation, a higher clock frequency must be used to increase the processing speed, thereby increasing the power consumption. Accordingly, the general-purpose DSP cannot be used for the portable equipment.
Since each of Japanese Laid-Open Publication Nos. 5-189470, 5-174046 and 5-189471 utilizes a digital processor dedicated to FFT, the same problems as those of the general-purpose DSP arise.